home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / pgp20src.zip / IDEA.C < prev    next >
C/C++ Source or Header  |  1992-08-09  |  16KB  |  526 lines
  1. /*    idea.c - C source code for IDEA block cipher.
  2.     IDEA (International Data Encryption Algorithm), formerly known as 
  3.     IPES (Improved Proposed Encryption Standard).
  4.     Algorithm developed by Xuejia Lai and James L. Massey, of ETH Zurich.
  5.     This implementation modified and derived from original C code 
  6.     developed by Xuejia Lai.  Last modified 8 July 92.
  7.  
  8.     Zero-based indexing added, names changed from IPES to IDEA.
  9.     CFB functions added.  Random number routines added.
  10.  
  11.     The IDEA(tm) block cipher is covered by a patent held by ETH and a
  12.     Swiss company called Ascom-Tech AG.  The Swiss patent number is
  13.     PCT/CH91/00117.  International patents are pending. IDEA(tm) is a
  14.     trademark of Ascom-Tech AG.  There is no license fee required for
  15.     noncommercial use.  Commercial users may obtain licensing details
  16.     from Dieter Profos, Ascom Tech AG, Solothurn Lab, Postfach 151, 4502
  17.     Solothurn, Switzerland, Tel +41 65 242885, Fax +41 65 235761.
  18.  
  19.     The IDEA block cipher uses a 64-bit block size, and a 128-bit key 
  20.     size.  It breaks the 64-bit cipher block into four 16-bit words
  21.     because all of the primitive inner operations are done with 16-bit 
  22.     arithmetic.  It likewise breaks the 128-bit cipher key into eight 
  23.     16-bit words.
  24.  
  25.     For further information on the IDEA cipher, see these papers:
  26.     1)    Xuejia Lai, "Detailed Description and a Software Implementation of 
  27.         the IPES Cipher", Institute for Signal and Information
  28.         Processing, ETH-Zentrum, Zurich, Switzerland, 1991
  29.     2)    Xuejia Lai, James L. Massey, Sean Murphy, "Markov Ciphers and 
  30.         Differential Cryptanalysis", Advances in Cryptology- EUROCRYPT'91
  31.  
  32.     This code assumes that each pair of 8-bit bytes comprising a 16-bit 
  33.     word in the key and in the cipher block are externally represented 
  34.     with the Most Significant Byte (MSB) first, regardless of the
  35.     internal native byte order of the target CPU.
  36.  
  37. */
  38. #include <stdio.h>
  39. #include "idea.h"
  40.  
  41. /* #define lower16(x) ((word16)((x) & mask16)) */ /* unoptimized version */
  42. #define lower16(x)   ((word16)(x))    /* optimized version */
  43.  
  44. #define maxim        0x10001
  45. #define fuyi         0x10000    /* Why did Lai pick a name like this? */
  46. #define mask16       ((word16) 0xffff)
  47. #define ROUNDS       8        /* Don't change this value, should be 8 */
  48.  
  49. static void en_key_idea(word16 userkey[8], word16 Z[6][ROUNDS+1]);
  50. static void de_key_idea(word16 Z[6][ROUNDS+1], word16 DK[6][ROUNDS+1]);
  51. static void cipher_idea(word16 inblock[4], word16 outblock[4],
  52.          word16 Z[6][ROUNDS+1]);
  53.  
  54.  
  55. /*    Multiplication, modulo (2**16)+1 */
  56. static word16 mul(register word16 a, register word16 b)
  57. {
  58.     register word32 q;
  59.     register long int p;
  60.     if (a==0)
  61.         p = maxim-b; 
  62.     else 
  63.         if (b==0)
  64.             p = maxim-a;  
  65.         else
  66.         {    q = (word32)a * (word32)b; 
  67.             p = (q & mask16) - (q>>16);
  68.             if (p<=0) 
  69.                 p = p+maxim;
  70.         }
  71.     return (lower16(p));
  72. }        /* mul */
  73.  
  74.  
  75. /*    Compute multiplicative inverse of x, modulo (2**16)+1,
  76.     using Euclid's GCD algorithm. */
  77. static word16 inv(word16 x)     
  78. {
  79.     long n1,n2,q,r,b1,b2,t;
  80.     if (x == 0)
  81.         b2 = 0;
  82.     else
  83.     {    n1 = maxim;
  84.         n2 = x;
  85.         b2 = 1;
  86.         b1 = 0;
  87.         do   
  88.         {    r = (n1 % n2);
  89.             q = (n1-r)/n2;
  90.             if (r == 0)  
  91.             {    if (b2 < 0)
  92.                     b2 = maxim+b2;
  93.             }
  94.             else
  95.             {    n1 = n2; 
  96.                 n2 = r; 
  97.                 t = b2;
  98.                 b2 = b1 - q*b2; 
  99.                 b1 = t;
  100.             }
  101.         } while (r != 0);
  102.     } 
  103. #ifdef IDEA_DEBUG
  104.     if ( mul(x, (word16) b2) != 1) /* check answer */
  105.         printf("\n\07Error! inv(%u) = %u ?\n", x, (word16) b2 );
  106. #endif
  107.     return ((word16) b2);
  108. }        /* inv */
  109.  
  110.  
  111. /*    Compute IDEA encryption subkeys Z */
  112. static void en_key_idea(word16 userkey[8], word16 Z[6][ROUNDS+1])
  113. {
  114.     word16 S[54];
  115.     int i,j,r;
  116.     /*   shifts   */
  117.     for (i = 0; i<8; i++)
  118.         S[i] = userkey[i];
  119.     for (i = 8; i<54; i++)
  120.     {    if ((i+2)%8 == 0)  /* for S[14],S[22],...  */  
  121.             S[i] = lower16((S[i-7] << 9) ^ (S[i-14] >> 7)); 
  122.         else
  123.             if ((i+1)%8 == 0)  /* for S[15],S[23],...   */
  124.             S[i] = lower16((S[i-15] << 9) ^ (S[i-14] >> 7)); 
  125.         else
  126.             S[i] = lower16((S[i-7] << 9) ^ (S[i-6] >> 7));
  127.     }
  128.     /* get subkeys */
  129.     for (r=0; r<ROUNDS+1; r++)
  130.         for (j=0; j<6; j++)
  131.             Z[j][r] = S[6*r + j];
  132.  
  133.     /* clear sensitive key data from memory... */
  134.     for (i=0; i<54; i++) S[i] = 0;
  135.  
  136. }        /* en_key_idea */
  137.  
  138.  
  139. /*    Compute IDEA decryption subkeys DK from encryption subkeys Z */
  140. static void de_key_idea(word16 Z[6][ROUNDS+1], word16 DK[6][ROUNDS+1])
  141. {  
  142.     int j;
  143.     for (j=0; j<ROUNDS+1; j++)
  144.     {    DK[0][ROUNDS-j] = inv(Z[0][j]);
  145.         DK[3][ROUNDS-j] = inv(Z[3][j]);
  146.         if (j==0 || j==ROUNDS)
  147.         {    DK[1][ROUNDS-j] = lower16(fuyi-Z[1][j]);
  148.             DK[2][ROUNDS-j] = lower16(fuyi-Z[2][j]);
  149.         }
  150.         else
  151.         {    DK[1][ROUNDS-j] = lower16(fuyi-Z[2][j]);
  152.             DK[2][ROUNDS-j] = lower16(fuyi-Z[1][j]);
  153.         }
  154.     }  
  155.     for (j=0; j<ROUNDS; j++)
  156.     {    DK[4][ROUNDS-1-j] = Z[4][j];
  157.         DK[5][ROUNDS-1-j] = Z[5][j];
  158.     }
  159. }        /* de_key_idea */
  160.  
  161.  
  162. /*    IDEA encryption/decryption algorithm */
  163. static void cipher_idea(word16 inblock[4], word16 outblock[4],
  164.          register word16 Z[6][ROUNDS+1])
  165. {    /* Note that inblock and outblock can be the same buffer */ 
  166.     int r;
  167.     register word16 x1, x2, x3, x4, kk, t1, t2, a;
  168.     x1=inblock[0];
  169.     x2=inblock[1];
  170.     x3=inblock[2];
  171.     x4=inblock[3];
  172.     for (r=0; r<ROUNDS; r++)
  173.     {    x1 = mul(x1, Z[0][r]);
  174.         x4 = mul(x4, Z[3][r]);
  175.         x2 = lower16(x2 + Z[1][r]);
  176.         x3 = lower16(x3 + Z[2][r]);
  177.         kk = mul(Z[4][r], (x1^x3));      
  178.         t1 = mul(Z[5][r], lower16(kk + (x2^x4)) );
  179.         t2 = lower16(kk + t1);
  180.         x1 = x1^t1;
  181.         x4 = x4^t2; 
  182.         a  = x2^t2;
  183.         x2 = x3^t1;
  184.         x3 = a;
  185.     }
  186.     outblock[0] = mul(x1, Z[0][ROUNDS]);
  187.     outblock[3] = mul(x4, Z[3][ROUNDS]);
  188.     outblock[1] = lower16(x3 + Z[1][ROUNDS]);
  189.     outblock[2] = lower16(x2 + Z[2][ROUNDS]);
  190. }        /* cipher_idea */
  191.  
  192.  
  193. /*-------------------------------------------------------------*/
  194.  
  195. #ifdef TEST
  196.  
  197. void main(void)
  198. {    /* Test driver for IDEA cipher */ 
  199.     int i, j, k; 
  200.     word16 Z[6][ROUNDS+1], DK[6][ROUNDS+1], XX[4], TT[4], YY[4];     
  201.     word16 userkey[8];
  202.  
  203.     /* Make a sample user key for testing... */
  204.     for(i=0; i<8; i++)
  205.         userkey[i] = i+1;
  206.  
  207.     /* Compute encryption subkeys from user key... */
  208.     en_key_idea(userkey,Z);
  209.     printf("\nEncryption key subblocks: ");
  210.     for(j=0; j<ROUNDS+1; j++) 
  211.     {    printf("\nround %d:   ", j+1);
  212.         if (j==ROUNDS)
  213.             for(i=0; i<4; i++)
  214.                 printf(" %6u", Z[i][j]);
  215.         else
  216.             for(i=0; i<6; i++)
  217.                 printf(" %6u", Z[i][j]);
  218.     }
  219.  
  220.     /* Compute decryption subkeys from encryption subkeys... */
  221.     de_key_idea(Z,DK);
  222.     printf("\nDecryption key subblocks: ");
  223.     for(j=0; j<ROUNDS+1; j++) 
  224.     {    printf("\nround %d:   ", j+1);
  225.         if (j==ROUNDS)
  226.             for(i=0; i<4; i++)
  227.                 printf(" %6u", DK[i][j]);
  228.         else
  229.             for(i=0; i<6; i++)
  230.                 printf(" %6u", DK[i][j]);
  231.     }
  232.  
  233.     /* Make a sample plaintext pattern for testing... */
  234.     for (k=0; k<4; k++)
  235.         XX[k] = k;
  236.  
  237.     cipher_idea(XX,YY,Z);       /* encrypt plaintext XX, making YY */ 
  238.  
  239.     cipher_idea(YY,TT,DK);      /* decrypt ciphertext YY, making TT */ 
  240.  
  241.     printf("\nX %6u   %6u  %6u  %6u \n",    
  242.       XX[0], XX[1],  XX[2], XX[3]);
  243.     printf("Y %6u   %6u  %6u  %6u \n",
  244.       YY[0], YY[1],  YY[2], YY[3]);
  245.     printf("T %6u   %6u  %6u  %6u \n",
  246.       TT[0], TT[1],  TT[2], TT[3]);
  247.  
  248.     /* Now decrypted TT should be same as original XX */
  249.     for (k=0; k<4; k++)
  250.         if (TT[k] != XX[k])
  251.         {    printf("\n\07Error!  Noninvertable encryption.\n");
  252.             exit(-1);    /* error exit */ 
  253.         }
  254.     printf("\nNormal exit.\n");
  255.     exit(0);    /* normal exit */ 
  256. }        /* main */
  257.  
  258.  
  259. #endif        /* TEST */
  260.  
  261.  
  262. /*************************************************************************/
  263.  
  264.  
  265. #define byteglue(lo,hi) ((((word16) hi) << 8) + (word16) lo)
  266.  
  267. /*
  268. **    xorbuf - change buffer via xor with random mask block
  269. **    Used for Cipher Feedback (CFB) or Cipher Block Chaining
  270. **    (CBC) modes of encryption.
  271. **    Can be applied for any block encryption algorithm,
  272. **    with any block size, such as the DES or the IDEA cipher.
  273. */
  274. static void xorbuf(register byteptr buf, register byteptr mask, register int count)
  275. /*    count must be > 0 */
  276. {    if (count) 
  277.         do
  278.             *buf++ ^= *mask++;
  279.         while (--count);
  280. }    /* xorbuf */
  281.  
  282.  
  283. /*
  284. **    cfbshift - shift bytes into IV for CFB input
  285. **    Used only for Cipher Feedback (CFB) mode of encryption.
  286. **    Can be applied for any block encryption algorithm with any 
  287. **    block size, such as the DES or the IDEA cipher.
  288. */
  289. static void cfbshift(register byteptr iv, register byteptr buf, 
  290.         register int count, int blocksize)
  291. /*     iv is the initialization vector.
  292.     buf is the buffer pointer.
  293.     count is the number of bytes to shift in...must be > 0.
  294.     blocksize is 8 bytes for DES or IDEA ciphers.
  295. */
  296. {    int retained;
  297.     if (count)
  298.     {    retained = blocksize-count;    /* number bytes in iv to retain */
  299.         /* left-shift retained bytes of IV over by count bytes to make room */
  300.         while (retained--)
  301.         {    *iv = *(iv+count);
  302.             iv++;
  303.         }
  304.         /* now copy count bytes from buf to shifted tail of IV */
  305.         do    *iv++ = *buf++;
  306.         while (--count);
  307.     }
  308. }    /* cfbshift */
  309.  
  310.  
  311.  
  312. /* Key schedules for IDEA encryption and decryption */
  313. static word16 Z[6][ROUNDS+1], DK[6][ROUNDS+1];
  314. static word16 (*keyschedule)[ROUNDS+1];    /* pointer to key schedule Z or DK */
  315. static word16 *iv_idea;        /* pointer to IV for CFB or CBC */
  316. static boolean cfb_dc_idea; /* TRUE iff CFB decrypting */
  317.  
  318.  
  319. /* initkey_idea initializes IDEA for ECB mode operations */
  320. void initkey_idea(byte key[16], boolean decryp)
  321. {
  322.     word16 userkey[8];    /* IDEA key is 16 bytes long */
  323.     int i;
  324.     /* Assume each pair of bytes comprising a word is ordered MSB-first. */
  325.     for (i=0; i<8; i++)
  326.     {    userkey[i] = byteglue(*(key+1),*key);
  327.         key++; key++;
  328.     }
  329.     en_key_idea(userkey,Z);
  330.     keyschedule = Z;
  331.     if (decryp)
  332.     {    int r,j;
  333.         de_key_idea(Z,DK);    /* compute inverse key schedule DK */
  334.         keyschedule = DK;
  335.         /* Don't need Z anymore.  Erase dangerous traces... */
  336.         for (r=0; r<ROUNDS+1; r++)
  337.             for (j=0; j<6; j++)
  338.                 Z[j][r] = 0;
  339.     }
  340.     for (i=0; i<8; i++)    /* Erase dangerous traces */
  341.         userkey[i] = 0;
  342. }    /* initkey_idea */
  343.  
  344.  
  345. /*    Run a 64-bit block thru IDEA in ECB (Electronic Code Book) mode,
  346.     using the currently selected key schedule.
  347. */
  348. void idea_ecb(word16 *inbuf, word16 *outbuf)
  349. {
  350.     /* Assume each pair of bytes comprising a word is ordered MSB-first. */
  351. #ifndef HIGHFIRST    /* If this is a least-significant-byte-first CPU */
  352.     /* Invert the byte order for each 16-bit word for internal use. */
  353.     union {
  354.         word16 w[4];
  355.         byte b[8];
  356.     } inbuf2, outbuf2;
  357.     register byte *p;
  358.     p = (byte *) inbuf;
  359.     inbuf2.b[1] = *p++;
  360.     inbuf2.b[0] = *p++;
  361.     inbuf2.b[3] = *p++;
  362.     inbuf2.b[2] = *p++;
  363.     inbuf2.b[5] = *p++;
  364.     inbuf2.b[4] = *p++;
  365.     inbuf2.b[7] = *p++;
  366.     inbuf2.b[6] = *p++;
  367.     cipher_idea(inbuf2.w,outbuf2.w,keyschedule);
  368.     /* Now invert the byte order for each 16-bit word for external use. */
  369.     p = (byte *) outbuf;
  370.     *p++ = outbuf2.b[1];
  371.     *p++ = outbuf2.b[0];
  372.     *p++ = outbuf2.b[3];
  373.     *p++ = outbuf2.b[2];
  374.     *p++ = outbuf2.b[5];
  375.     *p++ = outbuf2.b[4];
  376.     *p++ = outbuf2.b[7];
  377.     *p++ = outbuf2.b[6];
  378. #else    /* HIGHFIRST */
  379.     /* Byte order for internal and external representations is the same. */
  380.     cipher_idea(inbuf,outbuf,keyschedule);
  381. #endif    /* HIGHFIRST */
  382. }    /* idea_ecb */
  383.  
  384.  
  385. /*
  386. **    initcfb - Initializes the IDEA key schedule tables via key,
  387. **    and initializes the Cipher Feedback mode IV.
  388. **    References context variables cfb_dc_idea and iv_idea.
  389. */
  390. void initcfb_idea(word16 iv0[4], byte key[16], boolean decryp)
  391. /*     iv0 is copied to global iv_idea, buffer will be destroyed by ideacfb.
  392.     key is pointer to key buffer.
  393.     decryp is TRUE if decrypting, FALSE if encrypting.
  394. */
  395. {    iv_idea = iv0;
  396.     cfb_dc_idea = decryp;
  397.     initkey_idea(key,FALSE);
  398. } /* initcfb_idea */
  399.  
  400.  
  401. /*
  402. **    ideacfb - encipher a buffer with IDEA enciphering algorithm,
  403. **        using Cipher Feedback (CFB) mode.
  404. **
  405. **    Assumes initcfb_idea has already been called.
  406. **    References context variables cfb_dc_idea and iv_idea.
  407. */
  408. void ideacfb(byteptr buf, int count)
  409. /*    buf is input, output buffer, may be more than 1 block.
  410.     count is byte count of buffer.  May be > IDEABLOCKSIZE.
  411. */
  412. {    int chunksize;    /* smaller of count, IDEABLOCKSIZE */
  413.     word16 temp[IDEABLOCKSIZE/2];
  414.  
  415.     while ((chunksize = min(count,IDEABLOCKSIZE)) > 0)
  416.     {
  417.         idea_ecb(iv_idea,temp);  /* encrypt iv_idea, making temp. */ 
  418.  
  419.         if (cfb_dc_idea)    /* buf is ciphertext */
  420.             /* shift in ciphertext to IV... */
  421.             cfbshift((byte *)iv_idea,buf,chunksize,IDEABLOCKSIZE);
  422.  
  423.         /* convert buf via xor */
  424.         xorbuf(buf,(byte *)temp,chunksize); /* buf now has enciphered output */
  425.  
  426.         if (!cfb_dc_idea)    /* buf was plaintext, is now ciphertext */
  427.             /* shift in ciphertext to IV... */
  428.             cfbshift((byte *)iv_idea,buf,chunksize,IDEABLOCKSIZE);
  429.  
  430.         count -= chunksize;
  431.         buf += chunksize;
  432.     }
  433. } /* ideacfb */
  434.  
  435.  
  436. /*
  437.     close_idea function erases all the key schedule information when 
  438.     we are all done with a set of operations for a particular IDEA key 
  439.     context.  This is to prevent any sensitive data from being left 
  440.     around in memory.
  441. */
  442. void close_idea(void)    /* erase current key schedule tables */
  443. {    short r,j;
  444.     for (r=0; r<ROUNDS+1; r++)
  445.         for (j=0; j<6; j++)
  446.             keyschedule[j][r] = 0;
  447. }    /* close_idea() */
  448.  
  449. /********************************************************************/
  450.  
  451. /*
  452. **    These buffers are used by init_idearand, idearand, and close_idearand.
  453. */
  454. static word16 dtbuf_idea[4] = {0}; /* buffer for enciphered timestamp */
  455. static word16 randseed_idea[4] = {0}; /* seed for IDEA random # generator */
  456. static word16 randbuf_idea[4] = {0}; /* buffer for IDEA random # generator */
  457. static byte randbuf_idea_counter = 0;    /* # of random bytes left in randbuf_idea */
  458.  
  459. /*
  460. **    init_idearand - initialize idearand, IDEA random number generator.
  461. **        Used for generating cryptographically strong random numbers.
  462. **        Much of the design comes from Appendix C of ANSI X9.17.
  463. **        key is pointer to IDEA key buffer.
  464. **        seed is pointer to random number seed buffer.
  465. **        tstamp is a 32-bit timestamp
  466. */
  467. void init_idearand(byte key[16], byte seed[8], word32 tstamp)
  468. {    int i;
  469.     initkey_idea(key, FALSE);    /* initialize IDEA */
  470.  
  471.     for (i=0; i<4; i++)    /* capture timestamp material */
  472.     {    dtbuf_idea[i] = tstamp;    /* get bottom byte */
  473.         tstamp = tstamp >> 16;    /* drop bottom byte */
  474.         /* tstamp has only 4 bytes-- last 4 bytes will always be 0 */
  475.     }
  476.     /* Start with enciphered timestamp: */
  477.     idea_ecb(dtbuf_idea,dtbuf_idea);
  478.  
  479.     /* initialize seed material */
  480.     for (i=0; i<8; i++)
  481.         ((byte *)randseed_idea)[i] = seed[i];
  482.  
  483.     randbuf_idea_counter = 0;    /* # of random bytes left in randbuf_idea */
  484.  
  485. } /* init_idearand */
  486.  
  487.  
  488. /*
  489. **    idearand - IDEA pseudo-random number generator
  490. **        Used for generating cryptographically strong random numbers.
  491. **        Much of the design comes from Appendix C of ANSI X9.17.
  492. */
  493. byte idearand(void)
  494. {    int i;
  495.     if (randbuf_idea_counter==0)    /* if random buffer is spent...*/
  496.     {
  497.         /* Combine enciphered timestamp with seed material: */
  498.         for (i=0; i<4; i++)
  499.             randseed_idea[i] ^= dtbuf_idea[i];
  500.         idea_ecb(randseed_idea,randbuf_idea); /* fill new block */
  501.  
  502.         /* Compute new seed vector: */
  503.         for (i=0; i<4; i++)
  504.             randseed_idea[i] = randbuf_idea[i] ^ dtbuf_idea[i];
  505.         idea_ecb(randseed_idea,randseed_idea); /* fill new seed */
  506.  
  507.         randbuf_idea_counter = 8;    /* reset counter for full buffer */
  508.     }
  509.     /* Take a byte from randbuf_idea: */
  510.     return(((byte *)randbuf_idea)[--randbuf_idea_counter]);
  511. } /* idearand */
  512.  
  513.  
  514. void close_idearand(void)
  515. {    /* Erase random IDEA buffers and wipe out IDEA key info */
  516.     int i;
  517.     for (i=0; i<4; i++)
  518.     {    randbuf_idea[i] = 0;
  519.         randseed_idea[i] = 0;
  520.         dtbuf_idea[i] = 0;
  521.     }
  522.     close_idea();    /* erase current key schedule tables */
  523. }    /* close_idearand */
  524.  
  525. /* end of idea.c */
  526.